class Solution:
    def partition(self, s: str) -> list[list[str]]:
        def is_palindrome(sub: str) -> bool:
            """检查一个子串是否是回文串"""
            return sub == sub[::-1]

        def backtrack(start: int, path: list[str]):
            """回溯函数，start表示当前处理的起始位置，path表示当前的分割路径"""
            # 如果起始位置到达字符串末尾，说明找到了一个有效的分割方案
            if start == len(s):
                result.append(path[:])
                return
            
            # 尝试从当前起始位置开始的所有可能的分割点
            for end in range(start + 1, len(s) + 1):
                # 提取从start到end的子串
                sub = s[start:end]
                # 如果子串是回文串，则将其加入路径，并继续递归处理剩余部分
                if is_palindrome(sub):
                    path.append(sub)
                    backtrack(end, path)
                    path.pop()  # 回溯，移除最后一个加入的子串

        result = []
        backtrack(0, [])
        return result
    
param_1 = "aab"
solution = Solution()
ret = solution.partition(param_1)
print(ret)  # 输出: [["a", "a", "b"], ["aa", "b"]]